/*
 * BST.cpp
 *
 *  Created on: Jan 30, 2012
 *      Author: beebe
 */

#include "BST.h"
#include <assert.h>
#include <boost/lexical_cast.hpp>

//!  No-arg constructor.  Initializes an empty BST
BST::BST():root(NULL),size(0){}
BST::~BST(){
	Clear();
}
BST::BST(const BST & other):root(NULL),size(0){
	copyNodes(other.root);
}

BSTNode * BST::copyNodes(BSTNode * node){
	if(node==NULL)
		return NULL;
	this->Insert(node->value);
	copyNodes(node->GetLeft());
	copyNodes(node->GetRight());
	return NULL;
}


BST& BST::operator =(const BST & other){
	if(&other == this)
		return *this;
	Clear();
	this->copyNodes(other.root);
	return *this;
}


BSTNode * BST::GetRoot()const{
	return root;
}

bool BST::IsEmpty() const{
	return (size ==0);
}

void BST::Clear(){
	Clear(root);
	root = NULL;
}
void BST::Clear(BSTNode * node){
	if (node == NULL)
			return;
	Clear(node->left);
	Clear(node->right);

	delete node;
	size--;
}
int BST::GetSize() const{
	return size;
}

//!  Inserts value v into the BST
//!
//!  @param v The new value being inserted
//!
//!  @return a pointer to the newly inserted node, or NULL if v was already
//!          in the tree (i.e., NULL is used to indicate a duplicate insertion)
BSTNode * BST::Insert(const std::string & v){
	BSTNode * current = root;
	BSTNode * newnode = new BSTNode(v);
	if(current==NULL){
		root = newnode;
		size++;
		return newnode;
	}
	else while(current != NULL){
		if (v.compare(current->value)>0){
			if(current->GetRight() != NULL)
				current = current->GetRight();
			else{
				size++;
				current->right = newnode;
				return newnode;
			}
		} else if (v.compare(current->value)<0){
			if(current->GetLeft() != NULL){
				current = current->GetLeft();
			}else{
				size++;
				current->left = newnode;
				return newnode;
			}
		} else if (v.compare(current->value)==0){
			delete(newnode);
			current->count++;
			return NULL;
		}
	}
	return NULL;
}

//!  Searches the tree for value v
//!
//!  @param v The new value being searched for
//!
//!  @return a pointer to the node containing v, or NULL if v is not in the tree
BSTNode * BST::Find(const std::string & v) const{
	BSTNode * current = root;
	while(current != NULL){
		if (v.compare(current->value)>0)
			current = current->GetRight();
		else if (v.compare(current->value)<0)
			current = current->GetLeft();
		else if (v.compare(current->value)==0)
			return current;
	}
	return NULL;
}

std::string BST::toXmlString(BSTNode & current){
	std::string xmlOut = "";

	if(&current == NULL)
		return "";
	xmlOut += toXmlString(*current.left);
	xmlOut += "<occurrence><url>"+current.value+"</url>" +"<count>"+boost::lexical_cast<std::string>(current.count)+"</count></occurrence>";
	xmlOut += toXmlString(*current.right);
	return xmlOut;
}
std::string BST::toXmlDescString(BSTNode & current){
	std::string xmlOut = "";
	if(&current == NULL)
			return "";
	xmlOut += toXmlDescString(*current.left);
	StringUtil::EncodeToXml(current.description);
	xmlOut += "<page><url>"+current.value+"</url>" +"<description>"+current.description+"</description></page>";
	xmlOut += toXmlDescString(*current.right);
	return xmlOut;
}
